package hot100.logos51To60;

/**
 * @author logos
 * date 2025/7/15 19:06
 * @version v1.0
 * @Package hot100.logos51To60
 */
public class logos60 {

    /**
     * 60. 单词搜索
     * https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public boolean exist(char[][] board, String word) {
            char[] words = word.toCharArray();
            int n = board.length;
            int m = board[0].length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (dfs(board, words, i, j, 0)) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean dfs(char[][] board, char[] words, int i, int j, int k) {
            int n = board.length;
            int m = board[0].length;
            if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != words[k]) {
                return false;
            }
            board[i][j] = '0';
            if (k == words.length - 1) {
                return true;
            }
            boolean ans = dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i + 1, j, k + 1)
                    || dfs(board, words, i - 1, j, k + 1) || dfs(board, words, i, j - 1, k + 1);
            board[i][j] = words[k];
            return ans;
        }
    }
}
